Codeforces Round #104 (Div. 1 & Div. 2)

2A

弱智题，硬判即可。

Code

#include <cstdio>
#include <cstring>

char s[55];
int cnt1, cnt2, n, len, flag;

int main() {
    scanf("%d%s", &n, s + 1);
    len = strlen(s + 1);
    for (int i = 1; i <= len / 2; i++) {
        if (s[i] != '4' && s[i] != '7') flag = 1;
        else cnt1 += s[i] - '0';
    }
    for (int i = len / 2 + 1; i <= len; i++) {
        if (s[i] != '4' && s[i] != '7') flag = 1;
        else cnt2 += s[i] - '0';
    }
    if (cnt1 != cnt2 || flag) puts("NO");
    else puts("YES");
    return 0;
}

2B

注意到 $a,b\le 10^5$ ，所以上界为 $177777$ ，暴力枚举即可。

Code

#include <cstdio>
#include <cmath>

bool check(int x) { 
    return x == 4 || x == 7; 
}

int mask(int x) {
    int c = 0, ret = 0;
    for (; x; x /= 10) if (check(x % 10)) ret += x % 10 * pow(10, c++);
    return ret;
}

int main() {
    int a, b, c;
    scanf("%d%d", &a, &b);
    for (c = a + 1; c <= 177777; c++) if (mask(c) == b) break;
    printf("%d\n", c);
    return 0;
}

2C/1A

统计出所有 $i$ 满足 $a_i=4,\,b_i=7$ ，个数记为 $p$ 。所有 $j$ 满足 $a_j=7,\,b_j=4$ ，个数记为 $q$ ，容易证明答案为
$\max\{p,q\}$ 。

Code

#include <cstdio>
#include <cmath>

const int N = 1e5 + 5;

char a[N], b[N];
int n, cnt1, cnt2;

inline int min(int x, int y) {
    return x < y ? x : y;
}

int main() {
    scanf("%s%s", a + 1, b + 1);
    for (int i = 1; a[i]; i++) {
        if (a[i] == '4' && b[i] == '7') cnt1++;
        if (a[i] == '7' && b[i] == '4') cnt2++;
    }
    printf("%d\n", min(cnt1, cnt2) + abs(cnt1 - cnt2));
    return 0;
}

2D/1B

注意到 $47$ 和 $74$ 的个数至多差 $1$ ，于是考虑先把 $4$ 和 $7$ 交替排列，再把剩余的字符插入序列。

容易发现在交替排列之后，插入字符一定存在不会影响 $47$ 和 $74$ 个数的方案。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 5;

int ans[N], a[5];

int main() {
    cin >> a[1] >> a[2] >> a[3] >> a[4];
    if (abs(a[3] - a[4]) > 1 || 
        a[1] < a[3] || a[2] < a[3] || 
        a[1] < a[4] || a[2] < a[4]) puts("-1"), exit(0);
    int u = a[1], v = a[2], s = a[3], t = a[4], n = 1, flag = 0;
    ans[1] = 4, u--;
    while (s > 0 || t > 0) {
        n++;
        if (flag == 0) ans[n] = 7, v--, s--;
        else ans[n] = 4, u--, t--;
        flag ^= 1;
    }
    if (u < 0 || v < 0 || s < 0 || t < 0) {
        u = a[1], v = a[2], s = a[3], t = a[4], n = 1, flag = 1;
        ans[1] = 7, v--;
        while (s > 0 || t > 0) {
            n++;
            if (flag == 0) ans[n] = 7, v--, s--;
            else ans[n] = 4, u--, t--;
            flag ^= 1;
        }
        if (u < 0 || v < 0) puts("-1"), exit(0);
        putchar('7');
        for (int i = 1; i <= u; i++) putchar('4');
        if (ans[n] == 7) {
            for (int i = 2; i <= n; i++) putchar(ans[i] + '0');
            for (int i = 1; i <= v; i++) putchar('7');
        } else {
            for (int i = 2; i < n; i++) putchar(ans[i] + '0');
            for (int i = 1; i <= v; i++) putchar('7');
            putchar('4');
        }
    } else {
        for (int i = 1; i <= u + 1; i++) putchar('4');
        if (ans[n] == 7) {
            for (int i = 2; i <= n; i++) putchar(ans[i] + '0');
            for (int i = 1; i <= v; i++) putchar('7');
        } else {
            for (int i = 2; i < n; i++) putchar(ans[i] + '0');
            for (int i = 1; i <= v; i++) putchar('7');
            putchar('4');
        }
    }
}

2E/1C

待补。

1D

待补。

1E

一眼数据结构题，考虑线段树维护四种信息：

• 区间 $[l,r]$ 的最长不下降子序列。

• 区间 $[l,r]$ 的最长不上升子序列。

• 区间 $[l,r]$ 的数字 $4$ 的个数。

• 区间 $[l,r]$ 的数字 $7$ 的个数。

区间合并的方式显然，时间复杂度 $O(m\log n)$ 。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 4e6 + 5;

char s[N], op[N];

struct SegmentTree {
    int fr[N], sv[N], lazy[N], inc[N], dec[N];
    // inc: 最长不下降子序列
    // dec: 最长不上升子序列
    #define ls(u) u << 1
    #define rs(u) u << 1 | 1

    inline void pushup(int rt) {
        fr[rt] = fr[ls(rt)] + fr[rs(rt)];
        sv[rt] = sv[ls(rt)] + sv[rs(rt)];
        inc[rt] = max(inc[ls(rt)] + sv[rs(rt)], inc[rs(rt)] + fr[ls(rt)]);
        dec[rt] = max(dec[ls(rt)] + fr[rs(rt)], dec[rs(rt)] + sv[ls(rt)]);
    }

    inline void spread(int rt) {
        swap(fr[rt], sv[rt]);
        swap(inc[rt], dec[rt]);
        lazy[rt] ^= 1;
    }

    inline void pushdown(int rt) {
        if (lazy[rt]) {
            spread(ls(rt));
            spread(rs(rt));
            lazy[rt] = 0;
        }
    }

    void build(int rt, int l, int r) {
        if (l == r) {
            inc[rt] = dec[rt] = 1;
            s[l] == '4' ? fr[rt] = 1 : sv[rt] = 1;
            return void();
        }
        int mid = (l + r) >> 1;
        build(ls(rt), l, mid);
        build(rs(rt), mid + 1, r);
        pushup(rt);
    }

    void update(int rt, int l, int r, int x, int y) {
        if (x <= l && r <= y) return spread(rt);
        pushdown(rt);
        int mid = (l + r) >> 1;
        if (x <= mid) update(ls(rt), l, mid, x, y);
        if (y > mid) update(rs(rt), mid + 1, r, x, y);
        pushup(rt);
    }
} seg;

int main() {
    int n, m, l, r; 
    scanf("%d%d%s", &n, &m, s + 1);
    for (seg.build(1, 1, n); m; m--) {
        scanf("%s", op);
        if (op[0] == 'c') printf("%d\n", seg.inc[1]);
        if (op[0] == 's') scanf("%d%d", &l, &r), seg.update(1, 1, n, l, r);
    }
    return 0;
}